package com.acyouzi.leetcode.dp;

/**
 * 17/9/24 00:25
 *
 * @author sunxu
 */

//https://leetcode.com/problems/coin-change-2/description/
public class CoinChange2 {
  public static int change(int amount, int[] coins) {
    int[] dp = new int[amount+1];
    dp[0] = 1;
    for (int i : coins){
      for (int j = 1; j <= amount; j++) {
        if (j >= i) dp[j] = dp[j] + dp[j-i];
      }
    }
    return dp[amount];
  }

  public static void main(String[] args) {
    change(5,new int[]{1,2,5});
  }
}
